\section{Introducci\'on te\'orica}

\subsection{Algoritmos de búsqueda}

Los buscadores web son aquellos sitios que dada una palabra o frase encuentran las páginas que tienen lo que el usuario estaba buscando en una gran cantidad de casos. El secreto del éxito de estos buscadores no es sólo que encuentran el sitio con la palabra o frase deseada sino que encuentran el mejor resultado para esta. \\
Esto lo hace mediante métodos de rankeo que no son nada sencillos y es por eso que estaremos analizando 3 algoritmos distintos para hacerlo: PageRank, HITS e Indeg. Describiremos la idea teórica de cada uno, sus implementaciones y analizaremos cualitativa y temporalmente sus resultados. Es decir cuanto tardan en ejecutarse y que tan buenos son los resultados devueltos para distintas búsquedas. Procedamos entonces a explicar la idea de cada uno.

\subsubsection{PageRank}

El algoritmo de rankeo de sitios  llamado \textbf{PageRank} lo desarrollaron los fundadores de Google, Page y Brin, y fue tan revolucionario que cambió la forma en que se empezó a buscar en la web. \\
El primer punto de este algoritmo es mirar a la web como un grafo dirigido, donde cada nodo representa un sitio y los vértices van de un nodo a otro si un sitio contiene un link direccionando a este otro.
A partir de esto se define una \emph{matriz de vínculos} $M$, y como su nombre lo indica, esta representará las conectividades de los sitios pero con la particularidad de que tendrá información acerca de cuanto puntaje le asigna un sitio a otro, es decir, $m_{ij}$ será 1/$G_j$  (siendo $G_j$ el grado de salida del sitio $j$) si $j$ tiene un link a $i$ y 0 en otro caso.
De esta forma, la importancia de cada sitio esta medida por la calidad de sitios que linkean a cada uno, y a su vez la calidad esta conformada por la cantidad de sitios a los que redirijo, ya que si un sitio redirige a pocos sitios a cada uno estará otorgándole un puntaje cercano al 1, y en caso contrario el puntaje que otorgará sera cercano al 0 y no tendrá mucho peso a la hora de que los sitios de destino obtengan mayor importancia gracias a este.\\
Fácilmente se puede deducir que todas las columnas de la matriz resultante van a sumar 1, por lo que será una matriz \textit{``estocastica por columnas"}. Luego el problema de encontrar el ranking de cada cada sitio es equivalente a encontrar un $x\in \mathbb{R}^n$ tal que $Px = x$, es decir, encontrar (suponiendo que existe) un autovector asociado al autovalor 1 de una matriz cuadrada, tal que $x_i \ge
0$ y $\sum_{i = 1}^n x_i = 1$. 
\\
Uno puede abstraerse a la noción del \emph{navegante aleatorio}. Este vendría a representar cualquier usuario común que navega por la web a través de los links y que elige cualquiera de ellos con igual probabilidad.
\\
Un detalle importante que se debe considerar es que para que el PageRank funcione no puede haber nodos desconectados, ya que de ser así la matriz de vínculos no sería estocastica por columnas debido a que la columna de la matriz que representa a los sitios que linkea estarían todos en 0. La solución a esto vendría a ser la inversa del nodo, y es considerar a que el sitio esta conectado a \textbf{todos} los demás sitios, por lo que será equiprobable la navegación a cada uno de ellos. Para tal modificar se le debe hacer una modificación a la matriz original, con lo que si definimos $v \in \mathbb{R}^{n \times n}$, con $v_i = 1/n$ y $d \in \{0,1\}^{n}$ donde 
$d_i = 1$ si $G_i = 0$, y $d_i = 0$ en caso contrario, siendo $n$ la cantidad total de sitios web. La nueva matriz de transici\'on será:


\begin{eqnarray*}
D & = & v d^t \\
M_p & = & M + D.
\end{eqnarray*}
 

Además debemos considerar la noción de \emph{teletransportación}. Este vendría a representar cuando un usuario  decida visitar
una p\'agina cualquiera del conjunto, independientemente de si esta se encuentra o no referenciada por esa otra página. Para ello, consideramos que esta decisi\'on se toma con una probabilidad
$c \ge 0$, y podemos incluirlo al modelo de la siguiente forma:
\begin{eqnarray*}
E & = & v \bar{1}^t \\
M_f & = & cM_p + (1-c)E,
\end{eqnarray*}
\noindent donde $\bar{1} \in \mathbb{R}^n$ es un vector tal que todas sus componentes valen 1. Probabil\'isticamente, la
componente $x_j$ del vector soluci\'on (normalizado) del sistema $M_f x = x$ representa la proporci\'on del tiempo que,
en el largo plazo, el navegante aleatorio pasa en la p\'agina $j$. \\
Para llegar a la solución nos basaremos en el Método de la Potencia, que consiste en multiplicar la matriz sucesivamente a un vector inicial arbitrario hasta que la diferencia entre multiplicaciones sea ínfima. Esto se verá en la sección Desarrollo donde veremos la forma de implementación de la misma.


Una vez calculado el ranking, el resultado será el ranking de todas las páginas del conjunto.


\subsubsection{HITS}

Este algoritmo fué pensado por Kleinberg $[2]$ y su esencia está en la separación conceptual que hace entre un nodo \textit{autoridad} y uno \textit{Hub}. Vale aclarar que en este caso también entenderemos a un nodo como parte del grafo que modela a la internet y que representa a un sitio web en particular. \\
Autoridad serían aquellos sitios que tienen mayor importancia dentro de un tema específico y Hubs los que apuntan a estos sitios. En palabras mas terrenales las autoridades serían los que tienen las mejores respuestas y los hubs los que conocen a las mejores autoridades.
En la práctica se entiende por autoridades a aquellos nodos que son apuntados por una gran cantidad de sitios y por Hubs a los nodos a apuntan a muchos otros. Una web es mejor Autoridad si es apuntada por buenos Hubs y viceversa, un Hub es mejor si apunta a las mejores autoridades.\\
Para modelarlo computacionalmente pensamos a la red como una matriz $A \in \{0,1\}^{n \times n}$ donde cada fila y columna representan a un nodo y tienen un 1 si el nodo fila apunta al nodo columna o un 0 en caso contrario. Luego Kleinberg $[2]$  nos señala que debemos crear un vector \textit{x} e \textit{y} para agrupar las autoridades y hubs respectivamente. Estos vectores nos dice que los obtengamos tomando un x0 e y0 inciales con todos sus valores 1 y realizando este cálculo:

\begin{eqnarray}
x & = & A^ty \label{eq:auth-update-math} \\
y & = & Ax, \label{eq:hub-update-math} 
\end{eqnarray}

n veces (para un n definido) o hasta obtener un error menor a la tolerencia deseada. El error lo obtenemos calculando la norma manhattan entre el vector obtenido en el paso actual y el previo a este (mas adelante explicaremos como es la norma esta).\\
Luego de esto nos quedan en cada vector ordenados en el vector $x$ las mejores autoridades y en el $y$ los mejores hubs.

Dicho procedimiento debe aplicarse sobre una subred (denominada root-set) que debe calcularse previamente. Para esto mediante algún buscador simple, basado en texto por ejemplo, se acota la red a una determinada cantidad de nodos. Luego se le agregan aquellos que apuntan a algún nodo de dicha sub-red y los apuntados por esta, para finalmente sí, a este root-set aplicarle HITS. En este trabajo supondremos que este acotamiento previo ya fué efectuado.


\subsubsection{Indeg}
A modo de comparación para los experimentos, agregamos este algoritmo que resulta un poco inocente. Supongamos que tenemos una red de páginas, el peso, o importancia, de cada una será el promedio de la cantidad de links existentes en otras páginas del mismo conjunto hacia esta sobre la cantidad de links en total. El cálculo del mismo es lineal en la cantidad de referencias y su complejidad espacial es un vector de tamaño igual que el conjunto inicial de páginas. Este vector final es el resultado.

\begin{center}
$[k_1/n, k_2/n, ..., k_n/n]\quad 0 \leq k_i \leq n \quad n = cantTotalLinks$
\end{center}

\subsection{Método De La Potencia}
Durante el desarrollo de este trabajo utilizaremos el método de la potencia, utilizado para aproximar los autovalores y autovectores de una matriz. Como el informe no centra su análisis en cómo funciona este, recomendamos al lector informarse a cerca del mismo en [4].

\subsection{Norma Manhattan}

A lo largo de esta presentación, utilizaremos la distancia L1 entre dos vectores, también llamada Norma Manhattan.
La norma Manhattan es la suma de la diferencia coordenada a coordenada en modulo:

\begin{center}
$\left \| v - w \right \|_{1} = \sum_{i=1}^{n} \left | v_{i} - w_{i} \right |$
\end{center}

El uso del mismo estará detallado en el desarrollo de cada algoritmo presentado.

\subsection{Matriz Estocástica}
	Una matriz estocástica es aquella cuya suma de columnas o filas da 1, puede ser estocástica \textit{por columnas} o \textit{por filas} respectivamente.
	Formalmente es estócastica si:
	\begin{equation}
	\sum_j P_{i,j}=1 \ \ \ \ (por\ filas)
	\end{equation}
	\begin{center}ó\end{center}
		\begin{equation}
	 \sum_i P_{i,j}=1 \ \ \ \ (por\ columnas)
	\end{equation}
	

\subsection{Matriz Dispersa}
   Se define como matriz dispersa a aquella a la que la mayoría de sus elementos son cero.
   Ejemplo:

   $$ 
\begin{bmatrix}
       0    &      0    &   0       &   0           &   a_{04}    \\
       0    &   a_{11}  &   a_{12}  &   0           &   0    \\
       0    &      0    &   0       &   a_{23}      &   0    \\
       0    &      0    &   0       &   a_{33}      &   0    \\
  a_{40}    &      0    &   0       &   0           &   0    \\
\end{bmatrix} 
$$


\subsection{Almacenamiento de matrices dispersas}
 
 La matriz dispersa al tener la propiedad de tener muy pocos valores distintos de cero es conveniente solo guardar estos y asumir el resto como cero. Existen varias estructuras como Dictionary of Keys (DOK), Compressed Sparse Row (CSR) o Compressed Sparse Column (CSC) pensadas para optimizar el espacio y las operaciones con estas estructuras de datos.\\
 Veamos las características de cada una: 

\subsubsection{CSC}
Compressed Column Storage es una forma de almacenamiento para las matrices dispersas que se basa en el concepto de almacenar solo los elementos no-nulos de la matriz e información adicional para poder recorrerla y operar con ella normalmente. \\
En este caso su forma de almacenamiento consta de 3 arreglos y, como su nombre lo indica, destina un arreglo principal para almacenar los valores no-nulos de cada columna contiguos, y utiliza otro dos arreglos, uno del mismo tamaño del anterior que almacena el número de fila de cada elemento y otro de menor tamaño que contendrá las posiciones del arreglo principal en donde se producen los saltos de columna, que indica cuando un valor pertenece a la columna siguiente.

Veamos un ejemplo, suponiendo que tenemos la siguiente matriz:


   $$ 
\begin{bmatrix}
       0    &      0    &   0       &   0           &  4    \\
       9    &   1  &   3 &   0           &   0    \\
       0    &      0    &   0       &  2      &   0    \\
       0    &      7    &   0       &   6      &   2    \\
 5    &      0    &   0       &   0           &   0    \\
\end{bmatrix} 
$$
Los arreglos quedarán asi:


\[ valores= \left( \begin{array}{ccccccccc}
9 & 5 & 1 & 7 & 3 & 2 & 6 & 4 & 2\end{array} 
\right)\] 

\[ indice\ filas = \left( \begin{array}{ccccccccc}
2 & 5 & 2 & 4 & 2 & 3 & 4 & 1 & 4\end{array} 
\right)\] 

\[ puntero\ columnas = \left( \begin{array}{cccccc}
1 & 3 & 5 & 6 & 8 & 10\end{array} 
\right)\] 

\subsubsection{CRS}
Compressed Row Storage es otra forma de almacenamiento, análoga a CSC, con la diferencia de que en el segundo arreglo al que nos referimos anteriormente almacena el numero de columna de cada elemento y el tercer arreglo contiene las posiciones del arreglo principal en donde se producen saltos de fila.

Siguiendo el ejemplo anterior los arreglos quedarían:

\[ valores= \left( \begin{array}{ccccccccc}
4 & 9 & 1 & 3 & 2 & 7 & 6 & 2 & 5\end{array} 
\right)\] 

\[ indice\ columnas = \left( \begin{array}{ccccccccc}
5 & 1 & 2 & 3 & 4 & 2 & 4 & 5 & 1\end{array} 
\right)\] 

\[ puntero\ filas = \left( \begin{array}{cccccc}
1 & 2 & 5 & 6 & 9 & 10\end{array} 
\right)\] 

\subsubsection{DOK}
Dictionary of Keys se basa en otro concepto de almacenamiento de los valores no-nulos distinto de los anteriores. Como su nombre lo indica, es un diccionario en donde solo se almacenan los valores no-nulos y su posición como clave del mismo, cosa que nos asegura que no haya dos valores para una misma posición. Es decir, por cada elemento no nulo de la matriz el diccionario tendrá un elemento $<(fila, columna), valor>$

Continuando el ejemplo que usamos en las secciones anteriores, los elementos del diccionario serán:
\begin{center}

$<(1, 5), 4>$\\
$<(2, 1), 9>$\\
$<(2, 2), 1>$\\
$<(2, 3), 3>$\\
$<(3, 4), 2>$\\
$<(4, 2), 7>$\\
$<(4, 4), 6>$\\
$<(4, 5), 2>$\\
$<(5, 1), 5>$

\end{center}


\subsubsection{Elección}
Como las matrices que vamos a manejar son en su mayoría dispersas debíamos decidir una forma óptima de almacenarlas .
Entre las tres formas presentadas anteriormente terminamos eligiendo el Dictionary Of Keys. Tomamos esta decisión en función de lo que necesitábamos hacer y los tiempos que teníamos para hacerlo, y por tal motivo vimos que el DOK nos daba una mejor visualización de los datos. Si bien recorrer el DOK es mas complicado que en CSC o CRS porque los elementos no tienen un orden especifico, este tiene un fácil acceso a cada posición de la matriz sin necesidad de realizar cálculos extras, ventaja que termino pesando para la toma de decisión.  Otra característica que peso para la elección fue que las complejidades para las operaciones necesarias con la matriz eran muchos menores, y aún teniendo en cuenta que el almacenamiento requerido es mayor que para el de los otros dos, la diferencia no es tan grande y optamos por priorizar lo otro, ya que además cumple todas las expectativas y necesidades que requerimos para elaborar el informe y realizar los experimentos.




